package insert_sort

import (
	"learning/gooop/sorting"
)

type tInsertSort struct {
	fnInsert fnInsertFunction
}

func newInsertSort(usingBinarySearch bool) sorting.ISorter {
	it := &tInsertSort{
		nil,
	}
	if usingBinarySearch {
		it.fnInsert = binaryInsert
	} else {
		it.fnInsert = simpleInsert
	}
	return it
}

type fnInsertFunction func(data []interface{}, from int, to int, comparator sorting.CompareFunction)

// 插入排序
func (me *tInsertSort) Sort(data []interface{}, comparator sorting.CompareFunction) []interface{} {
	if data == nil {
		return nil
	}

	size := len(data)
	if size <= 1 {
		return data
	}

	for i := 1;i < size;i++ {
		me.fnInsert(data, 0, i, comparator)
	}

	return data
}

// 将位于to的值插入到有序序列data的[from,to)位置
func simpleInsert(data []interface{}, from int, to int, comparator sorting.CompareFunction) {
	for i := to;i>from;i-- {
		prev := i - 1
		if comparator(data[prev], data[i]) == sorting.GREATER {
			data[prev], data[i] = data[i], data[prev]
		} else {
			break
		}
	}
}

// 将位于to的值插入到有序序列data的[from,to)位置
func binaryInsert(data []interface{}, from int, to int, comparator sorting.CompareFunction) {
	p := binaryIndexOf(data, from, to - 1, data[to], comparator)
	if p != to {
		v := data[to]
		moveArrayRange(data, p, p + 1, to - p)
		data[p] = v
	}
}

// 整体移动数组的指定范围
func moveArrayRange(data []interface{}, src int, dst int, size int) {
	t := dst + size - 1
	for i := src + size - 1;i >= src;i-- {
		data[t] = data[i]
		t--
	}
}

// 二分查找首个>=v的下标
func binaryIndexOf(data []interface{}, from int, toInclusive int, v interface{}, comparator sorting.CompareFunction) int {
	for {
		if from == toInclusive {
			switch comparator(data[from], v) {
			case sorting.LESS:
				return from + 1

			default:
				return from
			}

		} else {
			p := (from + toInclusive) / 2
			switch comparator(data[p], v) {
			case sorting.LESS:
				from = min(p + 1, toInclusive)
				break

			case sorting.EQUAL:
				return p

			case sorting.GREATER:
				toInclusive = max(from, p - 1)
				break
			}
		}
	}
}

func min(a, b int) int {
	if a <= b {
		return a
	} else {
		return b
	}
}

func max(a, b int) int {
	if a >= b {
		return a
	} else {
		return b
	}
}

var SimpleInsertSorter = newInsertSort(false)
var BinaryInsertSorter = newInsertSort(true)